package Solution125_150;

import common.ListNode;
import org.junit.Test;

import java.util.LinkedList;

public class Solution143重排链表 {
    public void reorderList2(ListNode head) {
        if(head==null){
            return;
        }
        LinkedList<ListNode> list=new LinkedList<>();
        while (head!=null){
            list.addLast(head);
            head=head.next;
        }
        head=list.getFirst();
        list.removeFirst();
        boolean getLast=true;
        while (list.size()!=0){
            if(getLast){
                head.next=list.getLast();
                head=head.next;
                list.removeLast();
                getLast=false;
                if(list.size()==0){
                    head.next=null;
                }
            }else {
                head.next=list.getFirst();
                head=head.next;
                list.removeFirst();
                getLast=true;
                if(list.size()==0){
                    head.next=null;
                }
            }

        }
    }

    /**
     * 优解
     * @param head
     */
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;

        ListNode p1 = head;
        ListNode p2 = head;

        // 找到链表的一半
        while (p2.next != null && p2.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }

        // 将链表分为两段
        p2 = p1.next;
        p1.next = null;
        p1 = head;

        // 将后半段进行链表的翻转
        ListNode head2 = p2;
        ListNode next2;
        while (p2.next != null) {
            next2 = p2.next;
            p2.next = next2.next;
            next2.next = head2;
            head2 = next2;
        }
        p2 = head2;

        // 两条链表进行合并
        ListNode next1;
        while (p2 != null) {
            next1 = p1.next;
            next2 = p2.next;

            p1.next = p2;
            p2.next = next1;

            p1 = next1;
            p2 = next2;
        }

    }


    @Test
    public void test(){
        //1->2->3->4->5
        ListNode listNode1=new ListNode(1);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(3);
        ListNode listNode4=new ListNode(4);
        ListNode listNode5=new ListNode(5);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;

        reorderList(listNode1);
        System.out.println(listNode1);
    }
}
